//你正在使用一堆木板建造跳水板。有两种类型的木板，其中长度较短的木板长度为shorter，长度较长的木板长度为longer。你必须正好使用k块木板。编写一个方
//法，生成跳水板所有可能的长度。
//
// 返回的长度需要从小到大排列。
//
// 示例 1
//
// 输入：
//shorter = 1
//longer = 2
//k = 3
//输出： [3,4,5,6]
//解释：
//可以使用 3 次 shorter，得到结果 3；使用 2 次 shorter 和 1 次 longer，得到结果 4 。以此类推，得到最终结果。
//
// 提示：
//
//
// 0 < shorter <= longer
// 0 <= k <= 100000
//
//
// Related Topics 数组与矩阵 数学 👍 109 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
// 回溯set法解法(超时，可能去重后行)
function divingBoard(shorter: number, longer: number, k: number): number[] {


    function backtracking(temp) {
        if (temp.length === k) {
            set.add(temp.reduce((a,b) => a + b))
            return
        }
        for (let i = 0; i < num.length; i ++) {
            temp.push(num[i])
            backtracking(temp)
            temp.pop()
        }
    }
    let set : Set<number> = new Set<number>()
    let num : number[] = [shorter, longer]
    if (k === 0) return []
    backtracking([])
    return Array.from(set)


};
//leetcode submit region end(Prohibit modification and deletion)
//你正在使用一堆木板建造跳水板。有两种类型的木板，其中长度较短的木板长度为shorter，长度较长的木板长度为longer。你必须正好使用k块木板。编写一个方
//法，生成跳水板所有可能的长度。
//
// 返回的长度需要从小到大排列。
//
// 示例 1
//
// 输入：
//shorter = 1
//longer = 2
//k = 3
//输出： [3,4,5,6]
//解释：
//可以使用 3 次 shorter，得到结果 3；使用 2 次 shorter 和 1 次 longer，得到结果 4 。以此类推，得到最终结果。
//
// 提示：
//
//
// 0 < shorter <= longer
// 0 <= k <= 100000
//
//
// Related Topics 数组与矩阵 数学 👍 109 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
// 两个板子加起来是k个 这样遍历
function divingBoard2(shorter: number, longer: number, k: number): number[] {

    if (k === 0) return [];
    if (shorter === longer) return [k * shorter];
    let res = [];
    // 当我们短板有 i 个的时候，长板子就是 k-i 个，由于题目要求是将结果从小到大进行排序，那么我们起初就尽可能多的取短板子，最后结果就是通过 [0,k] 范围内遍历一遍即可
    for (let i = k; i >= 0; i--) {
        let shortCnt = i;
        let longCnt = k - i;
        let cnt = shortCnt * shorter + longCnt * longer;
        res.push(cnt);
    }
    return res;

};
//leetcode submit region end(Prohibit modification and deletion)
